\section{Heur'istica de B'usqueda Local}

\subsection{Introducci'on}

Como bien define el t'itulo de esta secci'on, lo que se pretende realizar en esta parte es hacer una b'usqueda. La idea es sencilla: a partir una soluci'on inicial $s_{inicial}$(que puede ser buena o no, solamente debe respetar las restricciones del problema), se busca mejorarla, explorando soluciones vecinas. Entonces, se define una vecindad N($s_{inicial}$) de la misma y se busca dentro de ese subconjunto de soluciones si existe alguna que sea mejor que la obtenida hasta el momento. Si es as'i procede a revisar la vecindad de la nueva soluci'on y as'i sucesivamente hasta que no se pueda mejorar m'as la soluci'on parcial. Eventualmente podr'iamos querer tener alg'un criterio de parada que la frene, dado que podr'iamos generar una vencidad tan grande que tuviera cantidad exponencial de vecinos con lo cual la complejidad podr'ia ser exponencial y queremos que sea polinomial. \\
Esta soluci'on parcial que encontramos, y no podemos mejorarla en su vecindad, es un 'optimo local de la funci'on objetivo (que puede ser un m'aximo o un m'inimo local dependiendo del problema en cuesti'on). No es la mejor soluci'on (no necesariamente al menos), pero es la mejor que podremos obtener partiendo de $s_{inicial}$. Podemos variar la soluci'on inicial y la definici'on de vecindad y obtener diferentes resultados. \textquestiondown Cu'al de las dos tendr'a m'as injerencia en el resultado?
\textquestiondown Obtendremos resultados mejores al partir de una mejor soluci'on inicial o ser'a mejor utilizar varias soluciones? Estas cuestiones son las que nos plantiamos en esta etapa del trabajo desarrollado y que trataremos de explicar durante toda la secci'on.\\
Dado que debemos proponer una heur'istica de busqueda local para el problema MAX-SAT, el cual es un poblema de maximizaci'on, nuestra heur'istica hallar'a un m'aximo local a partir de $s_{inicial}$ recorriendo las vecindad definidas para la funci'on objetivo.\\

\begin{figure}[H]
	\centering
		\includegraphics[width=0.4\textwidth]{dibujos/introBL.jpg}
	\caption{reprensentaci'on b'usqueda local}
\end{figure}

%Aca poner otro dibujito con circulitos, asi no queda tanta hoja en blanco

\newpage

\subsection{Soluci'on}

Para realizar la b'usqueda que nos lleve al m'aximo local de nuestra vecindad, debemos definir un punto de partida. Resulta conveniente partir de la soluci'on obtenida por la heur'istica constructiva ya que es una soluci'on aceptable y que probablemente podr'ia ser mejorada por m'as de un vecino en la vencidad.\\
El siguiente punto a discutir es c'omo definir la tan mencionada vencidad, como as'i tambi'en quienes ser'an los vecinos de la soluci'on inicial. Vamos a definir a una vecindad de la siguiente forma: Dado $S_{inicial}$ soluci'on inicial, la vecindad estar'a formada por todas las soluciones formadas a partir de alterar el valor de algunos de sus literales generando otras soluciones, es decir, elegir y cambiar el estado de $V_i$ y $V_j$ ,con $i$ y $j$ $\leq$ cantidad de variables. Por cada soluci'on generada de esta forma, vamos evaluando la cantidad de cl'ausulas satisfechas, si la cantidad es mayor, tomamos a la soluci'on evaluada como nuevo centro de la vecindad y repetimos el proceso hasta que no podamos mejorar m'as la cantidad de cl'ausulas satisfechas. En este punto habremos obtenido el m'aximo local que estabamos buscando.\\
Es importante mencionar que podr'iamos tener diversas variables de vecindad, con sus respectivos tama'nos. Dado que conocemos de antemano cu'an eficiente debe ser este procedimiento, algunas variantes fueron descartadas por no cumplir con la eficiencia solicita. \\
Se analizaron dos variantes: \\

\begin{itemize}
	\item{Alterar el valor de un literal genera un vecino:}
		\begin{itemize}
			\item con lo cual tenemos una vecindad de tama'no $\binom{v}{1}$, lo que recorrerla tiene un costo de O($v$), como consecuencia de probar todas las combinaciones de alterar el valor l'ogico de un literal en un conjunto que contiene, a lo sumo, v literales.
		\end{itemize}
	\item{Alterar el valor de, a lo sumo, dos literales genera un vecino:}
		\begin{itemize}
			\item en este caso una vecindad definida de esta forma tendr'ia tama'no $\binom{v}{2}$ , lo que recorrerla tiene un costo de O($v^{2}$), puesto que es probar todas las formas de alterar el valor l'ogico de dos literales para el conjunto de literales de la soluci'on con cardinal, a lo sumo, $v$.
		\end{itemize}
\end{itemize}

Otra variante ser'ia tomar de a tres literales e ir cambiandoles el valor en todas las formas posibles, pero esta vecindad es demasiado laxa haciendo que una exploraci'on de esta sea lo suficientemente costosa(Orden c'ubico respecto a literales). Se podr'ia reducir a explorar simplemente una porci'on de esta, pero a'un as'i ser'ia complejo determinar cuanto explorar y el porque de explorar siempre una determinada porci'on, por este motivo decidimos no incluir esta alternativa en este informe m'as all'a de que haya sido considerada una posibilidad muy interesante.\\
Tambi'en debemos mencionar que m'as all'a de que el fundamento principal de esta heur'istica es la exploraci'on dentro de una vecindad, no debemos descuidar como chequear si las soluciones vecinas mejorar o no. Este es un aspecto delicado y de vital importancia en la eficiencia que debe cumplir el algoritmo, estos detalles los mencionaremos m'as claramente en la secci'on de complejidad. 

\subsection{Pseudoc'odigo}

\newcommand{\busquedaLocal}{\ensuremath{\mbox{\sc busquedaLocal}}}
	\begin{algorithm}[H]
		\caption{\busquedaLocal(CasoDePrueba caso, $V$ resConstructiva)}\label{alg:busquedaLocal}
			\medskip
			\begin{algorithmic}[1]
			\STATE solucionMax $\leftarrow$  resConstructiva
			\FOR {i desde 0 .. $v$} 
				  \STATE j $\leftarrow$ 0
				  \WHILE{j desde 0 .. $v$ } 
					\STATE solucionesNuevas $\leftarrow$ crearNuevaSolucion(i,j, solucionMax)
					\IF {(clausulasSatisfechas(i, j, solucionesNuevas) $>$ solucionMax.cantClausulasSatisfechas)}
							\STATE solucionMax $\leftarrow$  solucionesNuevas
							\STATE i $\leftarrow$ 0 
							\STATE j $\leftarrow$ 0
							\STATE resetieContadores $\leftarrow$ true
							\IF {($c$ = solucionMax.cantClausulasSatisfechas)}
								\STATE devolver solucionMax 
							\ENDIF
					\ENDIF
					\IF {$\neg$resetieContadores}
						\STATE j $\leftarrow$ j + 1
					\ENDIF
					\STATE resetieContadores $\leftarrow$ false
				\ENDWHILE			
			\ENDFOR	
			\STATE devolver solucionMax
			\end{algorithmic}
	\end{algorithm}


\subsubsection{Explicaci'on}

La b'usqueda local comienza desde una soluci'on inicial, la propuesta por la Heur'istica Constructiva, la cual le asignamos a la solucionMax.\\
\textbf{matrizClausulas} es una matriz de cantidad de cl'ausulas filas (representando las cl'ausulas) * cantidad de variables * 2 columnas (representando las variables), en cada cl'ausula separamos en la primera mitad las variables positivas, en la segunda las negativas y colocamos un 1 si esa variable pertenece a la cl'ausula.\\
\textbf{contadorVariablesEnTrueMax} es un arreglo del tama'no de la cantidad de cl'ausulas donde en la posici'on i contamos la cantidad de variables que hacen verdadera a la  i-'esima cl'ausula.\\
\textbf{matrizClausulas} y \textbf{contadorVariablesEnTrueMax} los creamos solamente para poder determinar si una soluci'on mejora a otra en $O(C)$, con C cantidad de cl'ausulas (esto lo veremos m'as adelante).\\
Ahora hacemos un for y un while para ir variando las variables que vamos a modificar de la \textbf{solucionMax} y asignarla a \textbf{solucionesNuevas}. Esto es lo que hace el chequear2Variables seteando valores de matrizClausulas y contadorVariablesEnTrueMax por lo que mencionamos antes.\\
Luego si \textbf{solucionesNuevas} mejora a \textbf{solucionesMax}, est'a nueva pasa a ser la m'axima y seteamos los contadores en 0 para centrando as'i nuestra vecindad en esta nueva soluci'on encontrada.\\
Por 'ultimo, chequeamos si ya hicimos verdaderas todos las cl'ausulas para dejar de recorrer, porque 'esta ser'ia una soluci'on 'optima.\\
Terminamos devolviendo la solucionMax que es la 'optima local.  

\subsection{An'alisis de Complejidad}

Sean $C$ la cantidad de cl'ausulas y $V$ la cantidad de variables del caso de prueba:\\
Arrancamos el algoritmo partiendo de una soluci'on inicial que es la que nos da la Heur'istica Constructiva. Por lo tanto sumamos esta complejidad: O($C * V^{2}$).\\
Calculemos la complejidad de las primeras asignaciones:\\
\begin{itemize}
	\item llenarPositivosYNegativosMatriz: esta funci'on recorre todas las cl'ausulas y por cada una de ellas recorre las variables que contiene, que en peor caso podr'ian ser $2v$ armando una matriz de tama'no $(C * 2V)$. Con lo cual generarla tiene un costo de O($C * V$).
	\item contarValoresVerdaderos: esta funci'on chequea en cada clausula, utilizando la matriz y el binarioQueHaceMaxLasClausulas,de tama'no $v$, para saber cuantas variables(positivas o negativas) hacen verdadera la cl'ausula. O($C * V$).  
\end{itemize}}
Ahora bien, evaluemos el peor caso, el cual no llegamos a hacer verdaderas todas las cl'ausulas.\\
Tenemos un for y un while para ir cambiando de a lo sumo $2$ variables en la soluci'on.\\
Dentro, lo m'as costoso es chequear2variables. Esta funci'on es la que realiza el chequeo con las variables $i$ y $j$ seteando los valores de matrizClausulas y de contarVariablesEnTrueMax y armando una nueva soluci'on. El costo es el de recorrer las cl'ausulas. O($C$).\\ 
El resto son solamente comparaciones.\\
Pero si reseteamos los contadores, \textquestiondown{Qu'e cantidad de veces realizamos los ciclos?.\\
Hagamos una peque'na demostraci'on para ver esto:\\

\subsubsection{Demostraci'on}

El algoritmo comienza con una soluci'on constructiva que tiene $k$ cl'ausulas verdaderas. El algoritmo termina en $2$ casos, que no se pueda mejorar la cantidad de cl'ausulas satisfechas o que haga todas las cl'ausulas verdaderas.\\
\begin{itemize}
	\item primer caso: 0 $\leq$ $k$ $\leq$ $C$. Si no podemos mejorar m'as nuestra soluci'on entonces como m'aximo, si aumentamos en $1$ la cantidad de cl'ausulas satisfechas en cada paso, haremos $C$ - $k$ pasos.
	\item segundo caso: 0 $\leq$ $k$ $\leq$ $c$. Si llegamos a tener todas las cl'ausulas satisfechas, es porque si avanzamos de a $1$ la cantidad de cl'ausulas satisfechas en cada paso, haremos exactamente $C$ - $k$ pasos.   
\end{itemize}
Nuestro peor caso aqu'i ser'ia que $k$ sea 0. Por lo tanto la cantidad de veces que evaluariamos los ciclos es $C$


\title{Complejidad total}

Por lo tanto la complejidad nos queda : O($(C * V^{2}) + (C * 2V) + (C * V) + (V^{2} * C * C)$) $\in$ 

\fbox{O($C^{2} * V^{2}$)}

\newpage

\subsection{Experimentos y Gr'aficos}

En esta secci'on haremos dos tipos de pruebas, una para comparar la calidad de los resultados obtenidos y otra para evaluar la complejidad del algoritmo.\\
Utilizaremos en todos los casos el mismo criterio rand'omico para colocar variables en las distintas cl'ausulas que en la Heur'istica Constructiva.\\

\subsubsection{Resultados obtenidos}

Para empezar queremos ver si efectivamente mejoramos la Heur'istica de B'usqueda Local al cambiar a lo sumo dos variables en vez de solamente una.\\
Para ello tomamos dos casos de prueba.\\ 
El primero con 250 cl'ausulas, aumentando las variables hasta 50.\\ 
El segundo con 1000 cl'ausulas, aumentando las variables hasta 50.\\

  \begin{figure}[H]
  	\centering
  \includegraphics[width=0.9\textwidth]{./dibujos/BusquedaLocal/Comparacion_De_Resultados/250_clau_50_var_1_casodeprueba.png}
  	\caption{250 cl'ausulas y 50 variables.} 
  \end{figure}	 


  \begin{figure}[H]
  	\centering
  \includegraphics[width=0.9\textwidth]{./dibujos/BusquedaLocal/Comparacion_De_Resultados/1000_clau_50_var_1_casodeprueba.png}
  	\caption{1000 cl'ausulas y 50 variables.} 
  \end{figure}	 

Como vemos en los dos casos La Heur'istica de B'usqueda Local que modifica a lo sumo dos variables en varios casos mejora a la de solamente una. Nunca empeora ya que modificando a lo sumo dos variables tambien contemplamos el caso en el que modificamos una sola. As'i como no nos excedemos de la complejidad pedida, decidimos hacer el informe sobre 'este algoritmo.\\\\

\newpage

Ahora queremos comparar el algoritmo de Busqueda Local con el Exacto para observar que tan lejos quedamos de la soluci'on 'optima.\\
Corrimos 10 casos de prueba con 250 cl'ausulas y aumentando las variables hasta 14.\\

  \begin{figure}[H]
  	\centering
  \includegraphics[width=0.9\textwidth]{./dibujos/BusquedaLocal/Comparacion_De_Resultados/250_clau_15_var_10_casodeprueba.png}
  	\caption{exacto vs b'usqueda local.} 
  \end{figure}	 

Como podemos observar nuestro algoritmo de b'usqueda local est'a muy cerca o es igual a la soluci'on 'optima para estos casos.\\\\

\newpage
Veamos ahora la comparaci'on entre la heur'istica constructiva y la b'usqueda local.\\
Para ello tomamos un caso de prueba con 1000 cl'ausulas y hasta 100 variables.\\

  \begin{figure}[H]
  	\centering
  \includegraphics[width=0.9\textwidth]{./dibujos/BusquedaLocal/Comparacion_De_Resultados/1000_clau_100_var_1_casodeprueba.png}
  	\caption{constructiva vs b'usqueda local.} 
  \end{figure}	 

Podemos ver que en la mayor'ia de los casos mejoramos la soluci'on constructiva.\\\\

\newpage

\subsubsection{Complejidad}


Ahora comparemos la complejidad pr'actica del algoritmo con la te'orica calculada anteriormente.\\
Tomamos casos al azar con 200 cl'ausulas, aumentando las variables hasta 39, y casos al azar con 300 cl'ausulas, aumentando las variables hasta 25.\\
Medimos en escala logar'itmica para que se note mejor el gr'afico.\\
Queremos ver que la pr'actica est'e por debajo de la te'orica por alguna constante.\\


\begin{figure}[H]
 	\centering
\includegraphics[width=0.9\textwidth]{./dibujos/BusquedaLocal/Complejidad/BLocal_200_clas_39_vars_50_Rand_10_Casos_escala_log.png}
 	\caption{te'orica vs pr'actica .} 
\end{figure}	 



\begin{figure}[H]
 	\centering
\includegraphics[width=0.9\textwidth]{./dibujos/BusquedaLocal/Complejidad/BLocal_300_clas_25_vars_30_Rand_10_Casos_escala_log.png}
 	\caption{te'orica vs pr'actica .} 
\end{figure}	 

Se ve claramente que la complejidad te'orica multiplicada por una constante est'a por encima de la complejidad pr'actica del algoritmo como pensabamos.\\


Evaluamos 10 casos m'as en los cuales fijamos la cantidad de variables en 70 y aumentamos las cl'ausulas hasta 50.\\
En este caso la escala ser'a lineal para notar la diferencia.\\ 

\begin{figure}[H]
	\centering
\includegraphics[width=0.9\textwidth]{./dibujos/BusquedaLocal/Complejidad/BLocal_50_clas_70_vars_70_Rand_10_Casos_escala_normalVERSION_2.png}
 	\caption{te'orica vs pr'actica.} 
\end{figure}	 

Notamos en la mayor'ia de los gr'aficos una diferencia entre la complejidad pr'actica y la te'orica. Evaluando los casos llegamos a la conclusi'on de que en la te'orica acotamos por C a la cantidad de veces que el algoritmo podr'ia mejorar la soluci'on, o sea la cantidad de vecindades que recorre es como mucho la cantidad de cl'ausulas, pero en la pr'actica la cantidad de veces que mejora no es tan grande en casi ning'un caso.  

\subsection{Conclusiones}

En este ejercicio es interesante notar que manteniendo una complejidad de orden polinomial se puede mejorar la Heur'istica Constructiva planteada anteriormente. Mediante experimentos nos damos cuenta que aumentando muy poco la complejidad temporal del algoritmo podemos conseguir soluciones mejores en comparaci'on con la Constructiva.\\
Adem'as por las pruebas realizadas llegamos a la conclusi'on de que nuestra soluci'on esta bastante cerca de la que nos brinda el algoritmo exacto.\\
Notamos entonces la importancia de un algoritmo polinomial en el momento de la pr'actica, ya que es mucho menos costoso que un algoritmo exacto de orden exponencial. Lo que nos lleva a pensar que en muchos casos conviene usar esta Heur'istica, ya que se acerca bastante a devolver una soluci'on exacta y es mucho menos costosa.\\  